/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package btreetestat;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;
import java.util.List;
import java.util.Map.Entry;
import java.util.Set;

/**
 *
 * @author Yarolye
 */
public class BTreeController {

    private final int grad;
    int k;
    private TreeContainer startContainer;
    private int depth = 0;
    public static final int LEFT_NEIGHBOR = 0;
    public static final int RIGHT_NEIGHBOR = 1;

    public BTreeController(int k) {
        this.grad = 2 * k;
        this.k = k;
        startContainer = new TreeContainer();
    }

    public void pasteValue(int value) throws TreeException {
        TreeNode newNode = new TreeNode();
        newNode.setValue(value);
        TreeContainer targetContainer = findContainer(value, startContainer);
        if (targetContainer == null) {
            throw new TreeException("Fehler, es wurde kein Container für das Element gefunden");
        }
        if (targetContainer.containsKey(value)) {
            throw new TreeException("Das Element: " + value + " ist bereits vorhanden");
        }
        if (targetContainer.keySet().size() == grad) {
            splitContainer(targetContainer, newNode);
        } else {
            includeNode(newNode, targetContainer);
        }
    }

    private TreeContainer findContainer(int value, TreeContainer actualContainer) {
        //liefert den Container zurück, danach noch Prüfen ob das Element drin ist, oder der Container
        //voll ist

        if (actualContainer.isEmpty()) {
            return actualContainer;
        }
        if (actualContainer.containsKey(value)) {
            return actualContainer;
        }
        if (actualContainer.getHighestElement() < value) {
            //Wenn das zu suchende Element größer ist als die restlichen Werte im Container
            TreeNode lastNodeOfCont = actualContainer.lastEntry().getValue();
            if (lastNodeOfCont.getBiggerChildren() == null) {
                return actualContainer;
            } else {
                return findContainer(value, lastNodeOfCont.getBiggerChildren());
            }
        }
        for (Integer integer : actualContainer.keySet()) {
            if (value < integer) {
                TreeNode actualNode = actualContainer.get(integer);
                if (actualNode.getChildren() != null) {
                    return findContainer(value, actualNode.getChildren());
                } else {
                    return actualContainer;
                }
            }
        }
        //Wenn hierher gekommen dann stimmt was nicht
        return null;
    }

    private void splitContainer(TreeContainer actualContainer, TreeNode newNode) {

        int positionToSplit = actualContainer.size() / 2;
        TreeContainer newContainer = new TreeContainer();
        actualContainer.put(newNode.getValue(), newNode);

        TreeNode[] values = new TreeNode[actualContainer.values().size()];
        actualContainer.values().toArray(values);

        TreeNode oldParentNode = actualContainer.getParentNode();
        TreeContainer higherContainer = null;
        if (oldParentNode == null) { // wenn der oberste Knoten geteilt wird
            higherContainer = new TreeContainer();
            higherContainer.setParentNode(null);
            startContainer = higherContainer;
        }else{
            higherContainer=actualContainer.getParentNode().getTreeContainer();
        }        

        for (int i = positionToSplit + 1; i < values.length; i++) { // Entfernen der Knoten die Größer sind als der mittlere Wert
            TreeNode node = values[i];
            node.setLastNode(false);
            actualContainer.remove(node.getValue());
            newContainer.put(node.getValue(), node);
            node.setTreeContainer(newContainer);
        }
        TreeNode nodeToSplit = values[positionToSplit];
        actualContainer.remove(nodeToSplit.getValue());

        if (nodeToSplit.getChildren() != null) {                 //Umbiegen der bisherigen Kinder auf den Linken Teilbaum-das rechteste Element
            TreeNode lastEntry = actualContainer.lastEntry().getValue();
            lastEntry.setBiggerChildren(nodeToSplit.getChildren());
            nodeToSplit.getChildren().setParentNode(lastEntry);
        }
        if(nodeToSplit.getBiggerChildren() != null){
            TreeNode firstEntry = newContainer.firstEntry().getValue();
            firstEntry.setChildren(nodeToSplit.getBiggerChildren());
            nodeToSplit.getBiggerChildren().setParentNode(firstEntry);
        }
        if(oldParentNode==null){
           newContainer.setParentNode(nodeToSplit);    //wenn der Knoten in neuen Kontainer reinkommt
           nodeToSplit.setBiggerChildren(newContainer);
           nodeToSplit.setLastNode(true);
            
        }else if ( oldParentNode.getValue() < nodeToSplit.getValue()) {     //Wenn der Knoten der eine Ebene nach oben kommt, neuer letzter Knoten wird, bekommt er
            newContainer.setParentNode(nodeToSplit);    //auch  Die Knoten die Größer als er sind
            nodeToSplit.setBiggerChildren(newContainer);
            nodeToSplit.setLastNode(true);
            oldParentNode.setLastNode(false);
            oldParentNode.setBiggerChildren(null);
        } else if(oldParentNode.getValue()>nodeToSplit.getValue()){
            newContainer.setParentNode(oldParentNode);
            oldParentNode.setChildren(newContainer);
        }else  {                                              //am sonsten werden die Knoten an der alten Knoten
            newContainer.setParentNode(nodeToSplit);  //(der von dem die Referenz auf den Cont war)rangehängt
            nodeToSplit.setChildren(newContainer);
        }

        
        nodeToSplit.setChildren(actualContainer);       //den "kleiner"-zweig seten
        actualContainer.setParentNode(nodeToSplit);
        nodeToSplit.setTreeContainer(higherContainer);
        
        actualContainer.lastEntry().getValue().setLastNode(true);
        if (!higherContainer.isEmpty()) {                             // Wenn nicht der oberste Knoten modiffiziert wurde
            higherContainer.lastEntry().getValue().setLastNode(true);   // und es somit Werte in dem oberhalb ligenden Knoten gibt
        }
        includeNode(nodeToSplit, higherContainer);
    }

    private void includeNode(TreeNode newNode, TreeContainer actualContainer) {
        if (actualContainer.isEmpty()) {
            actualContainer.put(newNode.getValue(), newNode);
            newNode.setTreeContainer(actualContainer);
            newNode.setLastNode(true);
        } else {
            if (actualContainer.keySet().size() == grad) {
                splitContainer(actualContainer, newNode);
            } else {
                if (actualContainer.getHighestElement() < newNode.getValue()) {
                    newNode.setLastNode(true);//Wenn das neue Element das letzte in der Reihe ist, setzen das es das letzte ist
                    actualContainer.lastEntry().getValue().setLastNode(false);
                }
                actualContainer.put(newNode.getValue(), newNode);
                newNode.setTreeContainer(actualContainer);
            }
        }
    }

    public TreeContainer getStartContainer() {
        return startContainer;
    }

    public Integer getLowestElement(TreeContainer container) {
        if (container.isEmpty()) {
            return null;
        } else {
            TreeNode lowestElement = container.firstEntry().getValue();
            if (lowestElement.getChildren() == null) {
                return lowestElement.getValue();
            } else {
                return getLowestElement(lowestElement.getChildren());
            }
        }
    }

    public Integer getHighestElement(TreeContainer container) {
        if (container.isEmpty()) {
            return null;
        } else {
            TreeNode highestElement = container.lastEntry().getValue();
            if (highestElement.getBiggerChildren() == null) {
                return highestElement.getValue();
            } else {
                return getHighestElement(highestElement.getBiggerChildren());
            }
        }
    }

    public void removeValue(int value) throws TreeException {
        TreeContainer findContainer = findContainer(value, startContainer);
        if (!findContainer.containsKey(value)) {
            throw new TreeException("Der Wert " + value + " ist nicht verhanden");
        }
        TreeNode nodeToDelete = findContainer.get(value);
        if (nodeToDelete.getChildren() == null) {            //Wenn ein Blatt-Knoten gelöscht werden soll
            findContainer.remove(nodeToDelete.getValue());
            if (!findContainer.isEmpty() && nodeToDelete.isLastNode()) {
                findContainer.lastEntry().getValue().setLastNode(true);
            }
            if (findContainer.size() < k && findContainer != startContainer) {                      //Unterlauf findet statt
                rotate(findContainer);
            } else {
                //kein Unterlauf bei einem BLatt daher fertig
            }
        } else {
            removeInnerNode(findContainer, nodeToDelete);
        }
    }

    public void drawTree(TreeContainer container) {
        Collection<TreeNode> values = container.values();
        String output = "";
        for (TreeNode treeNode : values) {
            output = output + (treeNode.getValue() + "|");
        }
        for (int i = 0; i < depth; i++) {
//            System.out.print("\t");
        }
//        System.out.println(output);
        depth++;

        for (TreeNode treeNode : values) {
            if (treeNode.getChildren() != null) {
                drawTree(treeNode.getChildren());
            }
            if (treeNode.getBiggerChildren() != null) {
                drawTree(treeNode.getBiggerChildren());
            }
        }
        depth--;
    }

    private void rotate(TreeContainer unbalancedContainer) {
        TreeNode parentNode = unbalancedContainer.getParentNode();
        TreeContainer[] neighbors = getNeighbors(parentNode, unbalancedContainer);
        TreeContainer neighbor;
        if (neighbors[0] != null) {       //Ziemlich blöde Abfrage, heir wird der Nachbarkontainer ausgewählt
            neighbor = neighbors[0];        // dabei wird überprüft dass er nicht null ist und ob mit ihm rotiert werden kann
            if (neighbors[1] != null) {
                if (neighbors[0].size() <= k && neighbors[1].size() <= k) {
                    mixNode(unbalancedContainer, neighbors[0]);
                    return;
                } else {
                    if (neighbor.size() <= k) {
                        neighbor = neighbors[1];
                    }
                }
            } else {
                if (neighbors[0].size() <= k) {
                    mixNode(unbalancedContainer, neighbors[0]);
                    return;
                }
            }

        } else {
            neighbor = neighbors[1];
            if (neighbor == null || neighbors[1].size() <= k) {
                mixNode(unbalancedContainer, neighbors[1]);
                return;
            }
        }
        TreeNode newFatherNode;
        TreeContainer parentContainer = parentNode.getTreeContainer();
        if (neighbor == neighbors[LEFT_NEIGHBOR]) {
            parentNode = neighbor.getParentNode();
            newFatherNode = neighbor.lastEntry().getValue();// falls der nachbar links vom ausbalanciertem Knoten ist, braucht man das letzte Element
            neighbor.remove(newFatherNode.getValue());
            neighbor.lastEntry().getValue().setBiggerChildren(newFatherNode.getChildren());
            neighbor.lastEntry().getValue().setLastNode(true);
            parentContainer.remove(parentNode.getValue());
            parentContainer.put(newFatherNode.getValue(), newFatherNode);
            newFatherNode.setTreeContainer(parentNode.getTreeContainer());
            parentNode.setTreeContainer(unbalancedContainer);
            unbalancedContainer.put(parentNode.getValue(), parentNode);
            parentNode.setChildren(newFatherNode.getBiggerChildren());
            parentNode.setLastNode(false);
            parentNode.setBiggerChildren(null);
            newFatherNode.setChildren(neighbor);
            neighbor.setParentNode(newFatherNode);

            newFatherNode.setLastNode(false);
            parentContainer.lastEntry().getValue().setLastNode(true);
            if (newFatherNode.isLastNode()) {
                newFatherNode.setBiggerChildren(unbalancedContainer);
                unbalancedContainer.setParentNode(newFatherNode);
            }

        } else {
            parentNode = unbalancedContainer.getParentNode();
            newFatherNode = neighbor.firstEntry().getValue();               // am sonsten das erste vom rechten nachbar
            neighbor.remove(newFatherNode.getValue());
            parentContainer.remove(parentNode.getValue());
            parentContainer.put(newFatherNode.getValue(), newFatherNode);
            newFatherNode.setTreeContainer(parentContainer);
            parentNode.setTreeContainer(unbalancedContainer);
            unbalancedContainer.lastEntry().getValue().setLastNode(false);
            TreeContainer newChildrenForParentNode = unbalancedContainer.lastEntry().getValue().getBiggerChildren();
            unbalancedContainer.lastEntry().getValue().setBiggerChildren(null);
            unbalancedContainer.put(parentNode.getValue(), parentNode);
            parentNode.setLastNode(true);
            parentNode.setChildren(newChildrenForParentNode);
            if (newChildrenForParentNode != null) {
                newChildrenForParentNode.setParentNode(parentNode);
            }
            parentNode.setBiggerChildren(newFatherNode.getChildren());
            newFatherNode.setChildren(unbalancedContainer);
            unbalancedContainer.setParentNode(newFatherNode);
            newFatherNode.setLastNode(false);
            parentContainer.lastEntry().getValue().setLastNode(true);
            if (newFatherNode.isLastNode()) {
                newFatherNode.setBiggerChildren(neighbor);
                neighbor.setParentNode(newFatherNode);
            }
        }
    }

    private void mixNode(TreeContainer unbalancedContainer, TreeContainer neighbor) {
        TreeNode parentNodeUnbalanced = unbalancedContainer.getParentNode();
        TreeNode parentNodeNeighbor = neighbor.getParentNode();
        TreeNode parentToRemove=null;
        TreeContainer parentContainer = parentNodeUnbalanced.getTreeContainer();
        TreeContainer childrenForParentNode = null;
        Entry<Integer, TreeNode> lowerEntryOfParentContainer;
        Entry<Integer, TreeNode> higherEntryOfParentContainer;
        
        TreeNode[] neighborArr = new TreeNode[neighbor.size()];
        neighbor.values().toArray(neighborArr);

        if (unbalancedContainer.getHighestElement() < neighbor.getHighestElement()) {
            childrenForParentNode = unbalancedContainer.lastEntry().getValue().getBiggerChildren();
            unbalancedContainer.lastEntry().getValue().setBiggerChildren(null);
            parentToRemove=parentNodeUnbalanced;
        } else if (unbalancedContainer.getHighestElement() > neighbor.getHighestElement()) {
            childrenForParentNode = neighbor.lastEntry().getValue().getBiggerChildren();
            neighbor.lastEntry().getValue().setBiggerChildren(null);
            parentToRemove=parentNodeNeighbor;
        }

        lowerEntryOfParentContainer = parentContainer.lowerEntry(parentToRemove.getValue());
        higherEntryOfParentContainer = parentContainer.higherEntry(parentToRemove.getValue());
        
        parentContainer.remove(parentToRemove.getValue());
        parentToRemove.setTreeContainer(unbalancedContainer);
        parentToRemove.setChildren(childrenForParentNode);
        if(childrenForParentNode!=null)
        childrenForParentNode.setParentNode(parentToRemove);
        parentToRemove.setBiggerChildren(null);
        unbalancedContainer.lastEntry().getValue().setLastNode(false);
        unbalancedContainer.put(parentToRemove.getValue(), parentToRemove);
        if (parentToRemove.isLastNode()) {
            TreeNode previousNode = null;
            if (lowerEntryOfParentContainer != null && lowerEntryOfParentContainer.getValue() != null) {
                previousNode = parentContainer.lastEntry().getValue();
                previousNode.setBiggerChildren(unbalancedContainer);
                unbalancedContainer.setParentNode(previousNode);
            } else {
            }
            parentToRemove.setLastNode(false);
        } else {

            TreeNode nextNode = higherEntryOfParentContainer.getValue();
            nextNode.setChildren(unbalancedContainer);
            unbalancedContainer.setParentNode(nextNode);
        }

        for (int i = 0; i < neighborArr.length; i++) {
            neighborArr[i].setLastNode(false);
            unbalancedContainer.put(neighborArr[i].getValue(), neighborArr[i]);
            neighborArr[i].setTreeContainer(unbalancedContainer);
            neighbor.remove(neighborArr[i].getValue());
        }
        unbalancedContainer.lastEntry().getValue().setLastNode(true);
        if (parentContainer.isEmpty()) {
            startContainer = unbalancedContainer;
            startContainer.setParentNode(null);
        } else {
            parentContainer.lastEntry().getValue().setLastNode(true);
            if (parentContainer.size() < k && parentContainer != startContainer) {
                rotate(parentContainer);
            }
        }
    }

    private TreeContainer[] getNeighbors(TreeNode parentNode, TreeContainer unbalancedContainer) {
        TreeContainer[] neighbors = new TreeContainer[2];
        if (parentNode.getBiggerChildren() != null) {
            if (parentNode.getBiggerChildren() == unbalancedContainer) {
                neighbors[0] = parentNode.getChildren();
                neighbors[1] = null;
            } else {
                Entry<Integer, TreeNode> entryOfParentContainer = parentNode.getTreeContainer().lowerEntry(parentNode.getValue());
                if (entryOfParentContainer != null && entryOfParentContainer.getValue().getChildren() != unbalancedContainer) {
                    neighbors[0] = (entryOfParentContainer.getValue().getChildren());
                }
                neighbors[1] = parentNode.getBiggerChildren();
            }
        } else {
            Entry<Integer, TreeNode> entryOfParentContainer = parentNode.getTreeContainer().lowerEntry(parentNode.getValue());
            if (entryOfParentContainer != null && entryOfParentContainer.getValue().getChildren() != unbalancedContainer) {
                neighbors[0] = (entryOfParentContainer.getValue().getChildren());
            }
            entryOfParentContainer = parentNode.getTreeContainer().higherEntry(parentNode.getValue());
            if (entryOfParentContainer != null && entryOfParentContainer.getValue().getChildren() != unbalancedContainer) {
                neighbors[1] = entryOfParentContainer.getValue().getChildren();
            }
        }
        return neighbors;
    }

    private void removeInnerNode(TreeContainer findContainer, TreeNode nodeToDelete) {
        TreeNode smallerChild = nodeToDelete.getSmallerChild();
        TreeContainer smallerChildContainer = smallerChild.getTreeContainer();
        TreeContainer switchContainer;
        TreeNode nodeToSwitch;
        if (smallerChildContainer.size() > k) {
            nodeToSwitch = smallerChild;
        } else {
            nodeToSwitch = nodeToDelete.getBiggerChild();
        }
        TreeContainer childrenOfNodeToDelete = nodeToDelete.getChildren();
        TreeContainer biggerChildrenOfNodeToDelete = nodeToDelete.getBiggerChildren();

        switchContainer = nodeToSwitch.getTreeContainer();
        switchContainer.remove(nodeToSwitch.getValue());
        switchContainer.lastEntry().getValue().setLastNode(true);
        findContainer.remove(nodeToDelete.getValue());
        nodeToSwitch.setLastNode(nodeToDelete.isLastNode());
        nodeToSwitch.setTreeContainer(findContainer);
        nodeToSwitch.setChildren(childrenOfNodeToDelete);
        childrenOfNodeToDelete.setParentNode(nodeToSwitch);
        nodeToSwitch.setBiggerChildren(biggerChildrenOfNodeToDelete);
        if (biggerChildrenOfNodeToDelete != null) {
            biggerChildrenOfNodeToDelete.setParentNode(nodeToSwitch);
        }
        findContainer.put(nodeToSwitch.getValue(), nodeToSwitch);
        nodeToSwitch.setTreeContainer(findContainer);

        if (switchContainer.size() < k) {
            rotate(switchContainer);
        }
    }

    public int getK() {
        return k;
    }
    
}
